\chapter{Minkowski bound and class groups}
\label{ch:class_groups}
We now have a neat theory of unique factorization of ideals.
In the case of a PID, this in fact gives us a UFD. Sweet.

We'll define, in a moment, something called the \emph{class group}
which measures how far $\OO_K$ is from being a PID;
the bigger the class group, the farther $\OO_K$ is from being a PID.
In particular, $\OO_K$ is a PID if it has trivial class group.

Then we will provide some inequalities which let us put restrictions on the class group;
for instance, this will let us show in some cases that the class group must be trivial.
Astonishingly, the proof will use Minkowski's theorem, a result from geometry.

\section{The class group}
\prototype{PID's have trivial class group.}
Let $K$ be a number field,
and let $J_K$ denote the multiplicative group of fractional ideals of $\OO_K$.
Let $P_K$ denote the multiplicative group of \vocab{principal fractional ideals}:
those of the form $(x) = x \OO_K$ for some $x \in K$.
\begin{ques}
Check that $P_K$ is also a multiplicative group.
(This is really easy: name $x\OO_K \cdot y\OO_K$ and $(x\OO_K)\inv$.)
\end{ques}
As $J_K$ is abelian, we can now define the \vocab{class group} (or \vocab{ideal class group}) to be the quotient
\[ \Cl_K \defeq J_K / P_K. \]
The elements of $\Cl_K$ are called \vocab{classes}.

Equivalently,
\begin{moral}
The class group $\Cl_K$ is the set of nonzero fractional ideals modulo
scaling by a constant in $K$.
\end{moral}

You can also think of the classes as the ``shapes'' of the ideals,
as two ideals belong to the same class if and only if
they're isomorphic as $\OO_K$-modules.

\begin{example}[Ideal classes in $\QQ(\sqrt{-5})$]
	If the field is an imaginary quadratic field, visualizing the class of an ideal is really easy:
	because multiplication by a complex number corresponds to a combination of a scaling and a
	rotation (i.e. it preserves angles), two ideals belong to the same class if they are similar,
	that is, you can overlap one onto the another using rotation and scaling.

	When the field is $K = \QQ(\sqrt{-5})$, the ring of integers is $\OO_K = \ZZ[\sqrt{-5}]$.

	The first picture below depicts the ideal $(1) \subseteq \OO_K$. The second picture depicts $(2,
	1+\sqrt{-5}) \subseteq \OO_K$, which is not a principal ideal.
	\begin{center}
		\begin{asy}
			import graph;
			size(10cm);

			picture q;
			graph.xaxis(q, -5.2, 5.2);
			graph.yaxis(q, -5.2, 5.2);

			picture left, right;
			add(left, q); add(right, q);
			draw(left, yscale(sqrt(5))*unitsquare, cyan);
			draw(right, scale(2, 2*sqrt(5))*unitsquare, cyan);
			draw(right, rotate(angle(1+sqrt(5)*I)*180/pi)*scale(abs(1+sqrt(5)*I))*yscale(sqrt(5))*unitsquare, cyan);
			for(int x=-8; x<=8; ++x){
				for(int y=-8; y<=8; ++y){
					pair p=x+y*sqrt(5)*I;
					if(max(abs(p.x), abs(p.y))<=5){
						dot(left, p, blue);
						dot(right, p, (x+y)%2==0 ? blue: white*0.7
							);
					}
				}
			}

			add(currentpicture, left);
			add(currentpicture, shift(12, 0)*right);
		\end{asy}
	\end{center}
\end{example}

In particular, $\Cl_K$ is trivial if all ideals are principal,
since the nonzero principal ideals are the same up to scaling.

The size of the class group is called the \vocab{class number}.
It's a beautiful theorem that the class number is always finite,
and the bulk of this chapter will build up to this result.
It requires several ingredients.


\section{The discriminant of a number field}
\prototype{Quadratic fields.}
Let's say I have $K = \QQ(\sqrt 2)$.
As we've seen before, this means $\OO_K = \ZZ[\sqrt 2]$, meaning
\[ \OO_K = \left\{ a + b \sqrt 2 \mid a,b \in \ZZ \right\}. \]
The key insight now is that you might think of this as a \emph{lattice}:
geometrically, we want to think about this the same way we think about $\ZZ^2$.

Perversely, we might try to embed this into $\QQ^2$ by sending $a+b\sqrt 2$ to $(a, b)$.
But this is a little stupid, since we're rudely making $K$,
which somehow lives inside $\RR$ and is
``one-dimensional'' in that sense, into a two-dimensional space.
It also depends on a choice of basis, which we don't like.
A better way is to think about the fact that there are two embeddings
$\sigma_1 \colon K \to \CC$ and $\sigma_2 \colon K \to \CC$, namely the identity, and conjugation:
\begin{align*}
	\sigma_1(a+b\sqrt2) &= a+b\sqrt 2 \\
	\sigma_2(a+b\sqrt2) &= a-b\sqrt 2.
\end{align*}
Fortunately for us, these embeddings both have real image.
This leads us to consider the set of points
\[ \left( \sigma_1(\alpha), \sigma_2(\alpha) \right) \in \RR^2
\quad\text{as}\quad \alpha \in K. \]
This lets us visualize what $\OO_K$ looks like in $\RR^2$.
The points of $K$ are dense in $\RR^2$, but the points of $\OO_K$ cut out a lattice.

\begin{center}
	\begin{asy}
		size(8cm);
		real T = 1.414;
		int N = 10;
		real M = 5;
		for (int a = -N; a <= N; ++a) {
			for (int b = -N; b <= N; ++b) {
				if ((abs(a+T*b) <= M) && (abs(a-T*b) <= M))
				dot( (a+T*b, a-T*b) );
			}
		}
		draw( (-M,0)--(M,0), dotted);
		draw( (0,-M)--(0,M), dotted);
		label("$-2$", (-2,-2), dir(135));
		label("$-1$", (-1,-1), dir(135));
		label("$0$", (0,0), dir(135));
		label("$1$", (1,1), dir(135));
		label("$2$", (2,2), dir(135));
		label("$-\sqrt 2$", (-T,T), dir(135));
		label("$\sqrt 2$", (T,-T), dir(-45));
		label("$1+\sqrt 2$", (1+T,1-T), dir(-45));

		filldraw((0,0)--(1,1)--(1+T,1-T)--(T,-T)--cycle, heavycyan, blue);
	\end{asy}
\end{center}

To see how big the lattice is, we look at how $\{1, \sqrt2\}$, the generators
of $\OO_K$, behave.
The point corresponding to $a+b\sqrt2$ in the lattice is
\[ a \cdot (1,1) + b \cdot (\sqrt 2, -\sqrt 2). \]
The \vocab{mesh} of the lattice\footnote{Most authors call this the volume, but I
think this is not the right word to use -- lattices have ``volume'' zero since they
are just a bunch of points! In contrast, the English word ``mesh'' really
does refer to the width of a ``gap''.}
is defined as the hypervolume of the ``fundamental parallelepiped'' I've colored blue above.
For this particular case, it ought to be equal to the
area of that parallelogram, which is
\[
	\det
	\begin{bmatrix}
		1 & -\sqrt 2 \\
		1 & \sqrt 2
	\end{bmatrix}
	= 2\sqrt 2.
\]
The definition of the discriminant is precisely this, except with an extra square factor
(since permutation of rows could lead to changes in sign in the matrix above).
\Cref{prob:trace_discriminant} shows that the squaring makes $\Delta_K$ an integer.

To make the next definition, we invoke:
\begin{theorem}[The $n$ embeddings of a number field]
	Let $K$ be a number field of degree $n$.
	Then there are exactly $n$ field homomorphisms $K \injto \CC$,
	say $\sigma_1, \dots, \sigma_n$, which fix $\QQ$.
\end{theorem}
\begin{proof}
	Deferred to \Cref{thm:n_embeddings}, once we have the tools of Galois theory.
\end{proof}
In fact, in \Cref{thm:conj_distrb} we see that
for $\alpha \in K$, we have that $\sigma_i(\alpha)$
runs over the conjugates of $\alpha$ as $i=1,\dots,n$.
It follows that
\[
	\Tr_{K/\QQ}(\alpha) = \sum_{i=1}^n \sigma_i(\alpha)
	\quad\text{and}\quad
	\Norm_{K/\QQ}(\alpha) = \prod_{i=1}^n \sigma_i(\alpha).
\]

This allows us to define:
\begin{definition}
	Suppose $\alpha_1, \dots, \alpha_n$ is a $\ZZ$-basis of $\OO_K$.
	The \vocab{discriminant} of the number field $K$ is defined by
	\[
	\Delta_K \defeq \det
	\begin{bmatrix}
		\sigma_1(\alpha_1) & \dots & \sigma_n(\alpha_1) \\
		\vdots & \ddots & \vdots \\
		\sigma_1(\alpha_n) & \dots & \sigma_n(\alpha_n) \\
	\end{bmatrix}^2.
	\]
\end{definition}
This does not depend on the choice of the $\{\alpha_i\}$;
we will not prove this here.
\begin{example}[Discriminant of $K = \QQ(\sqrt2)$]
	We have $\OO_K = \ZZ[\sqrt 2]$
	and as discussed above the discriminant is
	\[
		\Delta_K =
		(-2 \sqrt 2)^2 = 8.
	\]
\end{example}
\begin{example}[Discriminant of $\QQ(i)$]
	Let $K = \QQ(i)$.
	We have $\OO_K = \ZZ[i] = \ZZ \oplus i \ZZ$.
	The embeddings are the identity and complex conjugation
	which take $1$ to $(1,1)$ and $i$ to $(i, -i)$.
	So
	\[
		\Delta_K =
		\det
		\begin{bmatrix}
			1 & 1 \\
			i & -i
		\end{bmatrix}^2
		=
		(-2i)^2 = -4.
	\]
	This example illustrates that the discriminant need not be positive
	for number fields which wander into the complex plane
	(the lattice picture is a less perfect analogy).
	But again, as we'll prove in the problems the discriminant is always
	an integer.
\end{example}
\begin{example}
	[Discriminant of $\QQ(\sqrt 5)$]
	Let $K = \QQ(\sqrt5)$.
	This time, $\OO_K = \ZZ \oplus \frac{1+\sqrt5}{2} \ZZ$, and so the discriminant
	is going to look a little bit different.
	The embeddings are still $a+b\sqrt 5 \mapsto a+b\sqrt5, a-b\sqrt5$.

	Applying this to the $\ZZ$-basis $\left\{ 1, \frac{1+\sqrt5}{2} \right\}$, we get
	\[
		\Delta_K
		=
		\det
		\begin{bmatrix}
			1 & 1 \\
			\frac{1+\sqrt5}{2} & \frac{1-\sqrt5}{2}
		\end{bmatrix}^2
		= (-\sqrt 5)^2 = 5.
	\]
\end{example}
\begin{exercise}
	Extend all this to show that
	if $K = \QQ(\sqrt d)$ for $d \neq 1$ squarefree, we have
	\[
		\Delta_K =
		\begin{cases}
			d & \text{if } d \equiv 1 \pmod 4 \\
			4d & \text{if } d \equiv 2, 3 \pmod 4.
		\end{cases}
	\]
\end{exercise}

Actually, let me point out something curious: recall that the polynomial discriminant of $Ax^2+Bx+C$ is $B^2-4AC$. Then:
\begin{itemize}
	\ii In the $d \equiv 1 \pmod 4$ case,
	$\Delta_K$ is the discriminant of $x^2 - x - \frac{d-1}{4}$,
	which is the minimal polynomial of $\half(1+\sqrt d)$.
	Of course, $\OO_K = \ZZ[\half(1+\sqrt d)]$.
	\ii In the $d \equiv 2,3 \pmod 4$ case,
	$\Delta_K$ is the discriminant of $x^2 - d$
	which is the minimal polynomial of $\sqrt d$. Once again, $\OO_K = \ZZ[\sqrt d]$.
\end{itemize}
This is not a coincidence! \Cref{prob:root_discriminant} asserts that this is true in general;
hence the name ``discriminant''.

\section{The signature of a number field}
\prototype{$\QQ(\sqrt[100]{2})$ has signature $(2, 49)$.}
In the example of $K = \QQ(i)$,
we more or less embedded $K$ into the space $\CC$.
However, $K$ is a degree two extension,
so what we'd really like to do is embed it into $\RR^2$.
To do so, we're going to take advantage of complex conjugation.

Let $K$ be a number field and $\sigma_1, \dots, \sigma_n$ be its embeddings.
We distinguish between the \vocab{real embeddings}
(which map all of $K$ into $\RR$)
and the \vocab{complex embeddings}
(which map some part of $K$ outside $\RR$).
Notice that if $\sigma$ is a complex embedding,
then so is the conjugate $\ol{\sigma} \neq \sigma$;
hence complex embeddings come in pairs.

\begin{definition}
	Let $K$ be a number field of degree $n$, and set
	\begin{align*}
		r_1 &= \text{number of real embeddings} \\
		r_2 &= \text{number of pairs of complex embeddings}.
	\end{align*}
	The \vocab{signature} of $K$ is the pair $(r_1, r_2)$.
	Observe that $r_1 + 2r_2 = n$.
\end{definition}
\begin{example}[Basic examples of signatures]
	\listhack
	\begin{enumerate}[(a)]
		\ii $\QQ$ has signature $(1,0)$.
		\ii $\QQ(\sqrt 2)$ has signature $(2,0)$.
		\ii $\QQ(i)$ has signature $(0,1)$.
		\ii Let $K = \QQ(\sqrt[3]{2})$, and let $\omega$ be a cube root of unity.
		The elements of $K$ are
		\[ K = \left\{ a + b\cbrt2 + c\cbrt4 \mid a,b,c \in \QQ  \right\}. \]
		Then the signature is $(1,1)$, because the three embeddings are
		\[ \sigma_1 \colon \cbrt 2 \mapsto \cbrt 2,
			\quad
			\sigma_2 \colon \cbrt 2 \mapsto \cbrt 2 \omega,
			\quad
			\sigma_3 \colon \cbrt 2 \mapsto \cbrt 2 \omega^2. \]
		The first of these is real and the latter two are conjugate pairs.
	\end{enumerate}
\end{example}
\begin{example}[Even more signatures]
	In the same vein $\QQ(\sqrt[99]{2})$ and $\QQ(\sqrt[100]{2})$
	have signatures $(1,49)$ and $(2,49)$.
\end{example}
\begin{ques}
	Verify the signatures of the above two number fields.
\end{ques}

From now on, we will number the embeddings of $K$ in such a way that
\[ \sigma_1, \sigma_2, \dots, \sigma_{r_1}  \]are the real embeddings,
while
\[
	\sigma_{r_1+1} = \ol{\sigma_{r_1+r_2+1}}, \quad
	\sigma_{r_1+2} = \ol{\sigma_{r_1+r_2+2}}, \quad
	\dots, \quad
	\sigma_{r_1+r_2} = \ol{\sigma_{r_1+2r_2}}.
\]
are the $r_2$ pairs of complex embeddings.
We define the \vocab{canonical embedding} of $K$ as
\[
	K \overset\iota\injto \RR^{r_1} \times \CC^{r_2} \
	\quad\text{by}\quad
	\alpha \mapsto  \left( \sigma_1(\alpha), \dots, \sigma_{r_1}(\alpha),
	\sigma_{r_1+1}(\alpha), \dots, \sigma_{r_1+r_2}(\alpha) \right).
\]
All we've done is omit, for the complex case, the second of the embeddings in each conjugate pair.
This is no big deal, since they are just conjugates;
the above tuple is all the information we need.

For reasons that will become obvious in a moment, I'll let $\tau$ denote the isomorphism
\[
	\tau \colon \RR^{r_1} \times \CC^{r_2} \taking{\sim} \RR^{r_1+2r_2} = \RR^n
\]
by breaking each complex number into its real and imaginary part, as
\begin{align*}
\alpha \mapsto  \big(& \sigma_1(\alpha), \dots, \sigma_{r_1}(\alpha), \\
& \Re \sigma_{r_1+1}(\alpha), \;\; \Im \sigma_{r_1+1}(\alpha), \\
& \Re \sigma_{r_1+2}(\alpha), \;\; \Im \sigma_{r_1+2}(\alpha), \\
& \dots, \\
& \Re \sigma_{r_1+r_2}(\alpha), \;\; \Im \sigma_{r_1+r_2}(\alpha) \big).
\end{align*}
\begin{example}[Example of canonical embedding]
	As before let $K = \QQ(\sqrt[3]{2})$ and set
	\[ \sigma_1 \colon \cbrt 2 \mapsto \cbrt 2,
		\quad
		\sigma_2 \colon \cbrt 2 \mapsto \cbrt 2 \omega,
		\quad
		\sigma_3 \colon \cbrt 2 \mapsto \cbrt 2 \omega^2 \]
	where $\omega = - \half + \frac{\sqrt3}{2} i$,
	noting that we've already arranged indices so $\sigma_1 = \id$ is real
	while $\sigma_2$ and $\sigma_3$ are a conjugate pair.
	So the embeddings $K \overset\iota\injto \RR \times \CC \taking\sim \RR^3$ are given by
	\[
		\alpha \overset\iota\longmapsto \left( \sigma_1(\alpha), \sigma_2(\alpha) \right)
		\overset\tau\longmapsto \left( \sigma_1(\alpha), \; \Re\sigma_2(\alpha), \; \Im\sigma_2(\alpha)  \right). \]
	For concreteness, taking $\alpha = 9 + \cbrt 2$ gives
	\begin{align*}
		9 + \cbrt 2 &\overset\iota\mapsto
		\left( 9 + \cbrt 2, \;\; 9 + \cbrt2\omega \right) \\
		&= \left( 9 + \cbrt 2, \;\;
		9 - \half\cbrt2 + \frac{\sqrt[6]{108}}{2} i  \right) \in \RR \times \CC \\
		&\overset\tau\mapsto \left( 9 + \cbrt 2, \;\; 9 - \half \cbrt 2,
		\;\; \frac{\sqrt[6]{108}}{2}  \right) \in \RR^3.
	\end{align*}
\end{example}

Now, the whole point of this is that we want to consider the resulting lattice
when we take $\OO_K$. In fact, we have:
\begin{lemma}
	\label{lem:vol_OK_mesh}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Then as before, $\OO_K$ becomes a lattice $L$ in $\RR^n$, with mesh equal to
	\[ \frac{1}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
\end{lemma}
\begin{proof}
	Fun linear algebra problem (you just need to manipulate determinants).
	Left as \Cref{prob:OK_linalg}.
\end{proof}
From this we can deduce:
\begin{lemma}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Let $\ka$ be an ideal in $\OO_K$.
	Then the image of $\ka$ is a lattice $L_\ka$ in $\RR^n$ with mesh equal to
	\[ \frac{\Norm(\ka)}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
\end{lemma}
\begin{proof}[Sketch of Proof]
	Let \[ d = \Norm(\ka) \defeq |\OO_K / \ka|. \]
	Then in the lattice $L_\ka$, we somehow only take $\frac 1d$th of the points
	which appear in the lattice $L$, which is why the area increases by a factor of $\Norm(\ka)$.
	To make this all precise I would need to do a lot more with lattices and geometry
	than I have space for in this chapter, so I will omit the details.
	But I hope you can see why this is intuitively true.
\end{proof}

\section{Minkowski's theorem}
Now I can tell you why I insisted we move from $\RR^{r_1} \times \CC^{r_2}$ to $\RR^n$.
In geometry, there's a really cool theorem of Minkowski's that goes as follows.
\begin{theorem}
	[Minkowski]
	Let $S \subseteq \RR^n$ be a convex set containing $0$
	which is centrally symmetric (meaning that $x \in S \iff -x \in S$).
	Let $L$ be a lattice with mesh $d$.
	If either
	\begin{enumerate}[(a)]
		\ii The volume of $S$ exceeds $2^n d$, or
		\ii The volume of $S$ equals $2^n d$ and $S$ is compact,
	\end{enumerate}
	then $S$ contains a nonzero lattice point of $L$.
\end{theorem}
\begin{ques}
	Show that the condition $0 \in S$ is actually extraneous
	in the sense that any nonempty, convex, centrally symmetric set contains the origin.
\end{ques}

\begin{proof}[Sketch of Proof]
	Part (a) is surprisingly simple and has a very olympiad-esque solution:
	it's basically Pigeonhole on areas.
	We'll prove part (a) in the special case $n=2$,
	$L = \ZZ^2$ for simplicity as the proof
	can easily be generalized to any lattice and any $n$.
	Thus we want to show that any such convex set $S$
	with area more than $4$ contains a lattice point.

	Dissect the plane into $2 \times 2$ squares
	\[ [2a-1, 2a+1] \times [2b-1, 2b+1] \]
	and overlay all these squares on top of each other.
	By the Pigeonhole Principle, we find there exist two points $p \neq q \in S$
	which is mapped to the same point.
	Since $S$ is symmetric, $-q \in S$. Then $\half (p-q) \in S$ (convexity) and is a nonzero lattice point.

	I'll briefly sketch part (b): the idea is to consider $(1+\eps) S$ for $\eps > 0$
	(this is ``$S$ magnified by a small factor $1+\eps$'').
	This satisfies condition (a). So for each $\eps > 0$ the set of nonzero lattice points in $(1+\eps) S$,
	say $S_\eps$, is a \emph{finite nonempty set} of (discrete) points
	(the ``finite'' part follows from the fact that $(1+\eps)S$ is bounded).
	So there has to be some point that's in $S_\eps$ for every $\eps > 0$ (why?), which implies it's in $S$.
\end{proof}

\section{The trap box}
The last ingredient we need is a set to apply Minkowski's theorem to.  I propose:
\begin{definition}
	Let $M$ be a positive real.
	In $\RR^{r_1} \times \CC^{r_2}$, define the box $S$ to be the
	set of points $(x_1, \dots, x_{r_1}, z_1, \dots, z_{r_2})$ such that
	\[
		\sum_{i=1}^{r_1} \left\lvert x_i \right\rvert
		+ 2 \sum_{j=1}^{r_2} \left\lvert z_j \right\rvert
		\le M.
	\]
	Note that this depends on the value of $M$.
\end{definition}

Think of this box as a \emph{mousetrap}: anything that falls in it is going to have a small norm,
and our goal is to use Minkowski to lure some nonzero element into it.

\begin{center}
	\begin{asy}
		size(6cm);
		real T = 1.414;
		int N = 10;
		real M = 3;

		real K = 2.4;
		filldraw( (K,0)--(0,K)--(-K,0)--(0,-K)--cycle, palered, darkred);
		label("$S$", (2*K/3,K/3), dir(45));

		for (int a = -N; a <= N; ++a) {
			for (int b = -N; b <= N; ++b) {
				if ((abs(a+T*b) <= M) && (abs(a-T*b) <= M))
				dot( (a+T*b, a-T*b) );
			}
		}
		draw( (-M,0)--(M,0), dotted);
		draw( (0,-M)--(0,M), dotted);
		label("$-2$", (-2,-2), dir(135));
		label("$-1$", (-1,-1), dir(135));
		label("$0$", (0,0), dir(135));
		label("$1$", (1,1), dir(135));
		label("$2$", (2,2), dir(135));
		label("$-\sqrt 2$", (-T,T), dir(135));
		label("$\sqrt 2$", (T,-T), dir(-45));
		label("$1+\sqrt 2$", (1+T,1-T), dir(-45));
	\end{asy}
\end{center}

That is, suppose $\alpha \in \ka$ falls into the box I've defined above, which means
\[
	M \ge
	\sum_{i=1}^{r_1} \left\lvert \sigma_i(\alpha) \right\rvert
	+ 2 \sum_{i=r_1+1}^{r_1+r_2} \left\lvert \sigma_i(\alpha) \right\rvert
	= \sum_{i=1}^{n} \left\lvert \sigma_i(\alpha) \right\rvert,
\]
where we are remembering that the last few $\sigma$'s come in conjugate pairs.
This looks like the trace, but the absolute values are in the way.
So instead, we apply AM-GM to obtain:
\begin{lemma}[Effect of the mousetrap]
	Let $\alpha \in \OO_K$, and suppose $\iota(\alpha)$ is in $S$
	(where $\iota \colon K \injto \RR^{r_1} \times \CC^{r_2}$ as usual).
	Then
	\[ \Norm_{K/\QQ}(\alpha)
		= \prod_{i=1}^n \left\lvert \sigma_i(\alpha) \right\rvert
		\le \left( \frac Mn \right)^n. \]
\end{lemma}
The last step we need to do is compute the volume of the box.
This is again some geometry I won't do, but take my word for it:
\begin{lemma}[Size of the mousetrap]
	Let $\tau \colon \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$ as before.
	Then the image of $S$ under $\tau$ is a convex, compact, centrally symmetric set with volume
	\[ 2^{r_1} \cdot \left( \frac{\pi}{2} \right)^{r_2} \cdot \frac{M^n}{n!}. \]
\end{lemma}
\begin{ques}
	(Sanity check)
	Verify that the above is correct for the signatures $(r_1, r_2) = (2,0)$ and $(r_1,r_2) = (0,1)$,
	which are the possible signatures when $n=2$.
\end{ques}


\section{The Minkowski bound}
We can now put everything we have together to obtain the great Minkowski bound.
\begin{theorem}
	[Minkowski bound]
	Let $\ka \subseteq \OO_K$ be any nonzero ideal.
	Then there exists $0 \neq \alpha \in \ka$ such that
	\[ \Norm_{K/\QQ}(\alpha) \le \left( \frac 4\pi \right)^{r_2} \frac{n!}{n^n} \sqrt{\left\lvert \Delta_K \right\rvert}
	\cdot \Norm(\ka). \]
\end{theorem}
\begin{proof}
	This is a matter of putting all our ingredients together.
	Let's see what things we've defined already:
	\begin{center}
	\begin{tikzcd}
		K \ar[r, "\iota", hook]
			& \RR^{r_1} \times \CC^{r_2} \ar[r, "\tau"]
			& \RR^n \\
		& \text{box } S \ar[r, mapsto]
			& \tau\im(S)
			& \quad\text{with volume }
			2^{r_1} \left( \frac\pi2 \right)^{r_2} \frac{M^n}{n!} \\
		\OO_K \ar[rr, mapsto]
			&& \text{Lattice } L
			& \quad\text{with mesh }
			2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \\
		\ka \ar[rr, mapsto]
			&& \text{Lattice } L_\ka
			& \quad\text{with mesh }
			2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \Norm(\ka)
	\end{tikzcd}
	\end{center}
	Pick a value of $M$ such that the mesh of $L_\ka$
	equals $2^{-n}$ of the volume of the box.
	Then Minkowski's theorem gives that some $0 \neq \alpha \in \ka$ lands inside the box ---
	the mousetrap is configured to force $\Norm_{K/\QQ}(\alpha) \le \frac{1}{n^n} M^n$.
	The correct choice of $M$ is
	\[
		M^n
		= M^n \cdot 2^n \cdot \frac{\text{mesh}}{\text{vol box}}
		= 2^n \cdot \frac{n!}{2^{r_1} \cdot \left( \frac \pi 2 \right)^{r_2}}
		\cdot 2^{-r_2} \sqrt{\left\lvert \Delta_K \right\rvert} \Norm(\ka)
	\]
	which gives the bound after some arithmetic.
\end{proof}

\section{The class group is finite}
\begin{definition}
	Let
	$M_K = \left( \frac 4\pi \right)^{r_2} \frac{n!}{n^n} \sqrt{\left\lvert \Delta_K \right\rvert}$
	for brevity.
	Note that it is a constant depending on $K$.
\end{definition}
So that's cool and all, but what we really wanted was to show that
the class group is finite.
How can the Minkowski bound help?
The key idea is the following:
\begin{moral}
	The class of $\ka$ is entirely determined by $(\alpha) \cdot \ka\inv$.
\end{moral}
\begin{ques}
	Verify this. (That is, if $\ka$ and $\kb$ are such that $(\alpha) \cdot \ka\inv = (\beta) \cdot
	\kb\inv$ for some $\alpha \in \ka$, $\beta \in \kb$, then prove that $\ka = (\gamma) \kb$
	for some $\gamma \in K$.)
\end{ques}

\begin{example}
	Recall this example:
	\[
		(6)
		= (2,1-\sqrt{-5})^2 (3,1+\sqrt{-5})(3,1-\sqrt{-5})
		= \kp^2 \kq_1 \kq_2. \]

	Consider $\ka = (2)$ being principal, pick $\alpha = 2$, then $(\alpha) \cdot \ka\inv = (1)$.
	If $(\alpha) \cdot \ka\inv = (1)$ (or $(2)$, or anything principal), we know $\ka$ must be
	principal.

	On the other hand, $\kq_1 = (3,1+\sqrt{-5})$ is not principal,
	pick $\alpha = 3$.
	We know $(3) = \kq_1 \kq_2$, so $(\alpha) \cdot \kq_1\inv = \kq_2 \neq (1)$.
\end{example}

In both examples above, $\ka \mid (\alpha)$, so their quotient should be an ``integer''. Indeed:
\begin{ques}
	Show that $(\alpha) \cdot \ka\inv$ is an integral ideal.
	(Unwind definitions.)
\end{ques}

You might notice that we can rewrite the Minkowski bound to say
\[ \Norm\left( (\alpha) \cdot \ka\inv \right) \le M_K \]
where $M_K$ is some constant depending on $K$.

This statement is helpful, because in fact, there are only finitely many integral ideals
with norm $\leq M_K$.

\begin{corollary}[Finiteness of class group]
	Class groups are always finite.
\end{corollary}
\begin{proof}
	We just have to show there are finitely many integral ideals as above;
	this will mean there are finitely many classes.

	Suppose we want to build such an ideal $\ka = \kp_1^{e_1} \dots \kp_m^{e_m}$.
	Recall that a prime ideal $\kp_i$ must have some rational prime $p$ inside it,
	meaning $\kp_i$ divides $(p)$ and $p$ divides $\Norm(\kp_i)$.
	So let's group all the $\kp_i$ we want to build $\ka$ with based on which $(p)$ they came from.
	\begin{center}
		\begin{asy}
			size(4cm);
			label("$(2)$", (1,0), dir(90));
			for (int i=1; i <= 4; ++i) dot( (1, -i/4) );
			label("$(3)$", (2,0), dir(90));
			for (int i=1; i <= 6; ++i) dot( (2, -i/4) );
			label("$(5)$", (3,0), dir(90));
			for (int i=1; i <= 2; ++i) dot( (3, -i/4) );
			label("$\dots$", (4,0), dir(90));
		\end{asy}
	\end{center}
	To be more dramatic: imagine you have a \emph{cherry tree};
	each branch corresponds to a prime $(p)$
	and contains as cherries (prime ideals) the factors of $(p)$ (finitely many).
	Your bucket (the ideal $\ka$ you're building) can only hold a total weight
	(norm) of $M_K$.  So you can't even touch the branches higher than $M_K$.
	You can repeat cherries (oops),
	but the weight of a cherry on branch $(p)$ is definitely $\ge p$;
	all this means that the number of ways to build $\ka$ is finite.
\end{proof}

\section{Computation of class numbers}
\begin{definition}
The order of $\Cl_K$ is called the \vocab{class number} of $K$.
\end{definition}
\begin{remark}
	If $\Cl_K = 1$, then $\OO_K$ is a PID, hence a UFD.
\end{remark}

By computing the actual value of $M_K$,
we can quite literally build the entire ``cherry tree'' mentioned in the previous proof.
Let's give an example how!
\begin{proposition}
	The field $\QQ(\sqrt{-67})$ has class number $1$.
\end{proposition}
\begin{proof}
	Since $K = \QQ(\sqrt{-67})$ has signature $(0,1)$
	and discriminant $\Delta_K = -67$ (since $-67 \equiv 1 \pmod 4$)
	we can compute
	\[ M_K = \left( \frac 4\pi \right)^{1} \cdot \frac{2!}{2^2} \sqrt{67} \approx 5.2. \]
	That means we can cut off the cherry tree after $(2)$, $(3)$, $(5)$, since any
	cherries on these branches will necessarily have norm $\ge M_K$.
	We now want to factor each of these in $\OO_K = \ZZ[\theta]$, where $\theta = \frac{1+\sqrt{-67}}{2}$
	has minimal polynomial $x^2 - x + 17$.
	But something miraculous happens:
	\begin{itemize}
		\ii When we try to reduce $x^2-x+17 \pmod 2$, we get an irreducible polynomial $x^2-x+1$.
		By the factoring algorithm (\Cref{thm:factor_alg}) this means $(2)$ is prime.
		\ii Similarly, reducing mod $3$ gives $x^2-x+2$, which is irreducible.
		This means $(3)$ is prime.
		\ii Finally, for the same reason, $(5)$ is prime.
	\end{itemize}
	It's our lucky day;
	all of the ideals $(2)$, $(3)$, $(5)$ are prime (already principal).
	To put it another way,
	each of the three branches has only one (large) cherry on it.
	That means any time we put together an integral ideal with norm $\le M_K$,
	it is actually principal.
	In fact, these guys have norm $4$, $9$, $25$ respectively\dots\
	so we can't even touch $(3)$ and $(5)$,
	and the only ideals we can get are $(1)$ and $(2)$ (with norms $1$ and $4$).

	Now we claim that's all.
	Suppose $\kb$ is an integral ideal such that $\Norm(\kb) \le M_K$.
	By the above, either $\kb = (1)$ or $\kb = (2)$, both of which are principal,
	and hence trivial in $\Cl_K$.
	So $J$ is trivial in $\Cl_K$ too, as needed.
\end{proof}
Let's do a couple more.
\begin{theorem}[Gaussian integers {$\ZZ[i]$} form a UFD]
	The field $\QQ(i)$ has class number $1$.
\end{theorem}
\begin{proof}
	This is $\OO_K$ where $K = \QQ(i)$, so we just want $\Cl_K$ to be trivial.
	We have $M_K = \frac{2}{\pi}\sqrt{4} < 2$.
	So every class
	has an integral ideal of norm $\kb$ satisfying
	\[
		\Norm(\kb)
		\le \left( \frac4\pi \right)^{1} \cdot \frac{2!}{2^2} \cdot \sqrt{4}
		= \frac4\pi < 2.
	\]
	Well, that's silly: we don't have any branches to pick from at all.
	In other words, we can only have $\kb = (1)$.
\end{proof}

Here's another example of something that still turns out to be unique factorization,
but this time our cherry tree will actually have cherries that can be picked.
\begin{proposition}[{$\ZZ[\sqrt7]$} is a UFD]
	The field $\QQ(\sqrt7)$ has class number $1$.
\end{proposition}
\begin{proof}
	First we compute the Minkowski bound.
	\begin{ques}
		Check that $M_K \approx 2.646$.
	\end{ques}
	So this time, the only branch is $(2)$. Let's factor $(2)$ as usual: the polynomial $x^2+7$
	reduces as $(x-1)(x+1) \pmod 2$, and hence
	\[ (2) = \left( 2, \sqrt7-1 \right) \left( 2, \sqrt7+1 \right). \]
	Oops! We now have two cherries, and they both seem reasonable.
	But actually, I claim that
	\[ \left( 2, \sqrt7-1 \right) = \left( 3 - \sqrt 7 \right). \]
	\begin{ques}
		Prove this.
	\end{ques}
	So both the cherries are principal ideals, and as before we conclude that $\Cl_K$ is trivial.
	But note that this time, the prime ideal $(2)$ actually splits; we got lucky
	that the two cherries were principal but this won't always work.
\end{proof}

How about some nontrivial class groups?
First, we use a lemma that will help us with
narrowing down the work in our cherry tree.
\begin{lemma}[Ideals divide their norms]
	\label{lemma:ideal_divides_norm}
	Let $\kb$ be an integral ideal with $\Norm(\kb) = n$.
	Then $\kb$ divides the ideal $(n)$.
\end{lemma}
\begin{proof}
	By definition, $n = \left\lvert \OO_K / \kb \right\rvert$.
	Treating $\OO_K/\kb$ as an (additive) abelian group and using Lagrange's theorem, we find
	\[ 0 \equiv
		\underbrace{\alpha + \dots + \alpha}_{n\text{ times}} = n\alpha
		\pmod \kb \qquad\text{for all } \alpha \in \OO_K. \]
	Thus $(n) \subseteq \kb$, done.
\end{proof}

Alternatively, if you have read \Cref{ch:galois_theory}:
If the extension $K/\QQ$ is Galois, we can actually prove that, analogous to
\Cref{remark:norm_equal_product_embeddings},
$\prod_{\sigma \in \Gal(K/\QQ)} \sigma(\kb) = (n)$, implying the result $id(\kb) \mid (n)$.

Now we can give such an example.
\begin{proposition}[Class group of $\QQ(\sqrt{-17})$]
	The number field $K = \QQ(\sqrt{-17})$ has class group $\Zc 4$.
\end{proposition}
You are not obliged to read the entire proof in detail,
as it is somewhat gory.
The idea is just that there are some cherries which are not trivial in the class group.
\begin{proof}
Since $\Delta_K = -68$, we compute
the Minkowski bound
\[ M_K = \frac{4}{\pi} \sqrt{17} < 6. \]

Now, it suffices to factor with $(2)$, $(3)$, $(5)$.
The minimal polynomial of $\sqrt{-17}$ is $x^2+17$, so as usual
\begin{align*}
	(2) &= (2, \sqrt{-17}+1)^2 \\
	(3) &= (3, \sqrt{-17}-1)(3,\sqrt{-17}+1) \\
	(5) &= (5)
\end{align*}
corresponding to the factorizations of $x^2+17$ modulo each of $2$, $3$, $5$.
Set $\kp = (2, \sqrt{-17}+1)$ and $\kq_1 = (3, \sqrt{-17}-1)$, $\kq_2 = (3, \sqrt{-17}+1)$.
We can compute
\[ \Norm(\kp) = 2 \quad\text{and}\quad \Norm(\kq_1) = \Norm(\kq_2) = 3. \]
In particular, they are not principal.
The ideal $(5)$ is out the window; it has norm $25$.
Hence, the three cherries are $\kp$, $\kq_1$, $\kq_2$.

The possible ways to arrange these cherries into ideals with norm $\le 5$ are
\[ \left\{ (1), \kp, \kq_1, \kq_2, \kp^2 \right\}. \]
However, you can compute \[ \kp^2 = (2) \] so $\kp^2$ and $(1)$ are in the same class group;
that is, they are trivial.
In particular, the class group has order at most $4$.

From now on, let $[\ka]$ denote the class (member of the class group) that $\ka$ is in.
Since $\kp$ isn't principal (so $[\kp] \neq [(1)]$), it follows that $\kp$ has order two.
So Lagrange's theorem says that $\Cl_K$ has order either $2$ or $4$.

Now we claim $[\kq_1]^2 \neq [(1)]$, which implies that $\kq_1$ has order greater than $2$.
If not, $\kq_1^2$ is principal.
We know $\Norm(\kq_1) = 3$,
so this can only occur if $\kq_1^2 = (3)$;
this would force $\kq_1 = \kq_2$.
This is impossible since $\kq_1 + \kq_2 = (1)$.

Thus, $\kq_1$ has even order greater than $2$.
So it has to have order $4$.
From this we deduce \[ \Cl_K \cong \Zc 4. \qedhere \]
\end{proof}

\begin{remark}
	When we did this at Harvard during Math 129,
	there was a five-minute interruption in which students (jokingly) complained
	about the difficulty of evaluating $\frac{4}{\pi} \sqrt{17}$. Excerpt:
	\begin{quotation}
		\footnotesize
		``Will we be allowed to bring a small calculator on the exam?'' -- Student 1 \\
		``What does the size have to do with anything?  You could have an Apple Watch'' -- Professor \\
		``Just use the fact that $\pi \ge 3$'' -- me \\
		``Even [other professor] doesn't know that, how are we supposed to?'' -- Student 2 \\
		``You have to do this yourself!'' -- Professor \\
		``This is an outrage.'' -- Student 1
	\end{quotation}
\end{remark}

\section{Optional: Proof that $\OO_K$ is a free $\ZZ$-module}

We have the suitable tools to prove \Cref{thm:OK_free_Z_module} now.

We know $\OO_K$ is a ring, so obviously it must be a $\ZZ$-module.
Suppose it is not a free $\ZZ$-module of degree $n = |K:\QQ|$. What could go wrong?
\begin{itemize}
	\ii First, it may happen that it is dense like $\QQ$ or the ring extension $\ZZ[\frac{1}{2}]$
	(which makes it not finitely generated and not free).
	\ii Even without that, it may happen that its rank is less than $n$.
\end{itemize}

The second possibility is much easier to discard.
Let $\alpha_1, \dots, \alpha_n$ be a basis of $K$.
Using \Cref{thm:rationalize_denom}, we have positive integers $d_1, \dots, d_n$ such that
$d_1 \alpha_1, \dots, d_n \alpha_n \in \OO_K$.
Since $\alpha_1, \dots, \alpha_n$ are linearly independent,
this implies $\rank \OO_K \geq n$.

The other direction is harder. We wish to prove $\OO_K$ is ``discrete'' in some sense.

From now on, replace $\alpha_i$ with $d_i \alpha_i$, so they are still a basis of the $\QQ$-vector
space $K$, and furthermore they are now in $\OO_K$.

\emph{Three} distinct proofs will be provided.

\subsection{First proof}
% lemma 2.9 in Neukirch

\begin{moral}
	We will show that $\OO_K$ is contained in some free $\ZZ$-module of rank $n$.
\end{moral}

Specifically, we will show that $\OO_K \subseteq \langle \frac{1}{d}\alpha_1, \dots,
\frac{1}{d}\alpha_n \rangle$ for some integer $d \neq 0$.

Let us pretend that we already know $\OO_K$ is a free $\ZZ$-module of
rank $n$. How would we compute $d$?

\begin{exercise}
	These are a few naive attempts to compute $d$; unfortunately, they wouldn't work. Verify that
	on $\langle 1, 1+2i \rangle \subseteq \ZZ[i]$.
	\begin{itemize}
		\ii Take $d$ to be the first positive integer that belongs to
		$\langle \alpha_1, \dots, \alpha_n \rangle$.
		(Attempt inspired by \Cref{thm:prime_ideals_over_rational}.)
		\ii Take $d$ to be the product of the norm of $\alpha_1, \dots, \alpha_n$.
	\end{itemize}
\end{exercise}

Instead, we compute $d$ by using an idea inspired by how we compute the mesh of the lattice.
Let $A = \langle \alpha_1, \dots, \alpha_n \rangle$, then it is a lattice and a free $\ZZ$-module of
rank $n$.

\begin{exercise}
	Assume you already know $\OO_K$ is free of rank $n$.
	Show that $|\OO_K/A|$ is finite.
	Conclude that for every $x \in \OO_K$, then $|\OO_K/A|
	\cdot x \in A$.
\end{exercise}

Using the same argument as \Cref{prob:trace_discriminant}, you can prove that the ``discriminant''
(squared mesh) of the lattice spanned by $\alpha_1, \dots, \alpha_n$ is an integer.
Formally, let \[ d \defeq \det
	\begin{bmatrix}
		\sigma_1(\alpha_1) & \dots & \sigma_n(\alpha_1) \\
		\vdots & \ddots & \vdots \\
		\sigma_1(\alpha_n) & \dots & \sigma_n(\alpha_n) \\
	\end{bmatrix}^2.  \]
\begin{exercise}
	Convince yourself (at least when all embeddings are real) that
	the ratio of the meshes of $\OO_K$ and $A$ is exactly
	the size of the quotient abelian group $\OO_K/A$, that is
	$\abs{\frac{d}{\Delta_K}} = |\OO_K/A|^2$.
	Conclude that for every $x \in \OO_K$, then
	$d \cdot x \in A$.
\end{exercise}
Which implies $\OO_K \subseteq \langle \frac{1}{d} \alpha_1, \dots, \frac{1}{d} \alpha_n \rangle$,
which is another free $\ZZ$-module of rank $n$.

However, the argument above is circular since it assumes $\Delta_K$ exists (it can only serve as a
motivation for where the value $d$ comes from).
The actual proof is the following.

Similar to \Cref{prob:trace_discriminant}, we define
\[ d \defeq \det [\TrK(\alpha_i \alpha_j)]_{i, j}. \]
Then, because $\{ \alpha_i \}_{i}$ spans $K$ as a $\QQ$-vector space,
there is some $\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \in \QQ^{\oplus n}$ such that
\[ \begin{bmatrix} \alpha_1 & \cdots & \alpha_n \end{bmatrix}
\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}
= \begin{pmatrix} x \end{pmatrix}. \]
Which means
\[ \begin{bmatrix}
	\TrK(\alpha_1 \alpha_1) & \cdots & \TrK(\alpha_1 \alpha_n) \\
	\vdots & \ddots & \vdots \\
	\TrK(\alpha_n \alpha_1) & \cdots & \TrK(\alpha_n \alpha_n)
\end{bmatrix}
\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}
= \begin{pmatrix} \TrK(\alpha_1 x) \\ \vdots \\ \TrK(\alpha_n x) \end{pmatrix}. \]
Or, in short,
\[
	(\text{some matrix $\in \GL_n(\ZZ)$ with determinant $d$}) \cdot
	\begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix}
	= (\text{some vector $\in \ZZ^{\oplus n}$}).
\]
\begin{ques}
	Finish the proof that $d \cdot x \in A$.
	(Cramer's rule. Or take the adjoint.)
\end{ques}

Finally, we have that $\OO_K$ is squeezed between two free $\ZZ$-modules of rank $n$, so it is
also free of rank $n$.\footnote{We did something similar in \Cref{remark:prime_ideals_are_maximal}.}
\begin{ques}
	Finish this. (\Cref{thm:fund_fg_abelian_group} can be used here.)
\end{ques}

\subsection{Second proof}
% chapter I, section 2, proposition 7 in Lang

This time around, instead of dividing by $d$, we instead take the \emph{dual lattice}.

What is the dual lattice, and why would we think about using it?
One way to motivate this proof is to look at the inverse of an ideal:
if $(1) \mid \ka$ (i.e. $\ka$ is an integral ideal), then $\ka\inv \mid (1)$.

Here, $\ka\inv \defeq \{ x \in K \mid x a \in \OO_K \text{ for all }a \in \ka\}$.

We can think of doing something similar, considering
\[
	\{ x \in K \mid x a \in \OO_K \text{ for all }a \in \langle \alpha_1, \dots, \alpha_n\rangle \}.
\]
This set is actually a lattice of rank $n$, but this won't work to prove the argument!
We're trying to prove $\OO_K$ is ``discrete'' in the first place, if $\OO_K = K$ then the set above
would equal $K$ as well.

Instead, we must rely on what we already know --- the discreteness of $\ZZ$.
Define
\[
	S \defeq \{ x \in K \mid \TrK(x a) \in \ZZ \text{ for all }a \in
	\langle \alpha_1, \dots, \alpha_n\rangle \}.
\]
This set is a bit larger than the previous set.
\begin{ques}
	Verify that this set is a superset of the previous one. Then conclude that $\OO_K \subseteq S$.
\end{ques}
\begin{exercise}
	Consider $\langle 1, 2i \rangle \subseteq \ZZ[i]$. What would the set $S$ be? (Recall that the
	trace in $\CC$ is just twice the real part.)
\end{exercise}

$S$ is still a lattice of rank $n$ --- and this time, we can actually prove it! Since we already
know $\ZZ$ is discrete.

Now, this is a purely algebraic problem,
we will only need to use knowledge of vector space here.
Each element $x \in K$ can be written as a vector
\[ F(x) \defeq \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \in \QQ^{\oplus n} \]
if we use the basis $\{ \alpha_1, \dots, \alpha_n \}$.

\begin{exercise}
	Show that $(x, y) \mapsto \TrK(x \cdot y)$ can then be written as an \emph{invertible} matrix in
	$\GL_n(\QQ)$ ---
	specifically, there exists $M \in \GL_n(\QQ)$ such that $\TrK(x \cdot y) = F(x)^\top M F(y)$,
	where $F(x)^\top$ is the transpose of $F(x)$.
\end{exercise}

Which makes $(x, y) \mapsto \TrK(x \cdot y)$ \emph{almost} an inner product
(see \Cref{ch:inner_product_spaces}),
except that it is not positive definite (for example, in $\CC$, we have $\Tr((1+i)^2) = 0$).
But having the matrix invertible suffices to do the following:

\begin{exercise}
	Finish the proof. (Hint: Consider the matrix
	$\begin{bmatrix} F(\alpha_1) & \cdots & F(\alpha_n) \end{bmatrix} \in \GL_n(\QQ)$.
	What is the condition on $F(x)$ such that $x \in S$?)
\end{exercise}

\subsection{Third proof}

Recall that we wish to prove $\OO_K$ is a free $\ZZ$-module of rank $n$.
To do that, we suppose it cannot be generated by $n$ elements, then show that $\OO_K$ is not
discrete, and this causes trouble because we know the norm is continuous.
\begin{exercise}
	Consider $K \cong \QQ^{\oplus n}$, this gives a topology on $K$.
	Verify that $x \mapsto |\Norm(x)|$ is indeed continuous.
\end{exercise}
We have that for every $x \in \OO_K$, then $|\Norm(x)| \in \ZZ$.
\begin{exercise}
	Conclude that there is a ball $B(0, r)$ in the topology above that contains no element of
	$\OO_K$, except $0$.
\end{exercise}

Now, what goes wrong if $\OO_K$ cannot be generated by $n$ elements? Things go wrong quickly:
\begin{exercise}
	Suppose $\langle \alpha_1, \dots, \alpha_n \rangle$ generates $K$ as a $\QQ$-vector space.
	Let $x \in \OO_K$ such that $x$ is not a $\ZZ$-linear combination of $\{ \alpha_1, \dots,
	\alpha_n \}$.
	Show that there is $z_1, \dots, z_n \in [-\frac{1}{2}, \frac{1}{2}]$ not all zero,
	and $z$ a $\ZZ$-linear combination of $\{ \alpha_1, \dots, \alpha_n \}$
	such that $x + z = \sum_{i=1}^n z_i \alpha_i$.
\end{exercise}
\begin{exercise}
	With notation as above, suppose $z_1 \neq 0$. Show that if we replace $\alpha_1$ with $z_1$,
	then the new set $\{ z_1, \alpha_2, \dots, \alpha_n \}$ still spans $K$ as a $\QQ$-vector space;
	furthermore, the mesh of the lattice gets decreased by \emph{at least a half}.
\end{exercise}

\begin{example}
	Suppose $A \subseteq \CC$ is a lattice. We know $1 \in A$ and $i \in A$,
	so $\ZZ[i] \subseteq A$.

	Assume we know in addition that $2.3 - 3.1i \in A$.
	\begin{center}
		\begin{asy}
			import graph;
			for(int x=-4; x<=4; ++x){
				for(int y=-4; y<=4; ++y){
					dot((x, y), blue);
				}
			}
			dot(2.3 - 3.1I, red);
			graph.xaxis(-4.5, 4.5);
			graph.yaxis(-4.5, 4.5);
		\end{asy}
	\end{center}

	Because $A$ is closed under addition, we know that $(2.3 - 3.1i) + (-2 + 3i) = 0.3-0.1i \in A$.
	We replace $1$ in the basis with $0.3-0.1i$.
	Then, the lattice $\langle i, 0.3-0.1i\rangle \subseteq A$ has smaller mesh than $\langle 1, i
	\rangle$ as expected.
	\begin{center}
		\begin{asy}
			import graph;
			for(int x=-8; x<=8; ++x){
				for(int y=-20; y<=20; ++y){
					pair p=x*I+y*(0.3-0.1I);
					if(max(abs(p.x), abs(p.y))<=4.2){
						dot(p, ((x, y)==(0, 1) ? red: blue));
					}
				}
			}
			graph.xaxis(-4.5, 4.5);
			graph.yaxis(-4.5, 4.5);
		\end{asy}
	\end{center}
\end{example}

Since we can do this indefinitely ($\OO_K$ never gets spanned), the mesh decreases to $0$ rapidly.

So, are we done? Since the mesh goes to $0$, maybe the smallest distance of some $\alpha_i$ also go
to $0$? Almost, but not quite:
\begin{example}
	Consider $\alpha_1 = 1+3i$ and $\alpha_2 = 2+7i$.
	\begin{center}
		\begin{asy}
			import graph;
			pair a=1, b=I;
			a+=3*b;
			b+=2*a;
			//write(a, b, a+b);
			filldraw(origin--a--a+b--b--cycle, orange, orange*0.2);
			dot("$\alpha_1$", a, blue);
			dot("$\alpha_2$", b, blue, align=dir(135));
			graph.xaxis(xmin=-11, xmax=11);
			graph.yaxis(ymin=-11, ymax=11);
		\end{asy}
	\end{center}
	The mesh of the lattice spanned by $\alpha_1$ and $\alpha_2$ is $1$,
	however, neither $\alpha_1$ nor $\alpha_2$ are particularly close to the origin.
\end{example}
We need to apply Minkowski bound here again: suppose the mesh is $d$, then
the cube centered at origin with volume $2^n d$ contains a nonzero lattice point.\footnote{Using a
sphere would of course make for a better bound, but its volume is a bit harder to calculate.}
This point's distance cannot be more than $\sqrt{n} \cdot \sqrt[n]{d}$ away from the origin.

\begin{remark}
	Speaking of which, the LLL lattice basis reduction algorithm can be used to find \emph{in
	practice} a point on the lattice that is \emph{close enough} to the origin.
\end{remark}

For $d$ small enough, $\sqrt{n} \cdot \sqrt[n]{d} < r$ where $r$ is the ball of no lattice point we
have shown above, which gives a contradiction. So we're done!

\section\problemhead
\begin{problem}
	Show that $K = \QQ(\sqrt{-163})$ has trivial class group,
	and hence $\OO_K = \ZZ\left[ \frac{1+\sqrt{-163}}{2} \right]$
	is a UFD.\footnote{In fact,
		$n = 163$ is the largest number
		for which $\QQ(\sqrt{-n})$ has trivial class group.
		The complete list is $1, 2, 3, 7, 11, 19, 43, 67, 163$,
		the \vocab{Heegner numbers}.
		You might notice Euler's prime-generating polynomial $t^2+t+41$
		when doing the above problem.  Not a coincidence!}
	\begin{hint}
		Repeat the previous procedure.
	\end{hint}
\end{problem}

\begin{problem}
	Determine the class group of $\QQ(\sqrt{-31})$.
	\begin{hint}
		You should get a group of order three.
	\end{hint}
\end{problem}

\begin{problem}[China TST 1998]
	Let $n$ be a positive integer.
	A polygon in the plane (not necessarily convex) has area greater than $n$.
	Prove that one can translate it so that it contains at least $n+1$ lattice points.
	\begin{hint}
		Mimic the proof of part (a) of Minkowski's theorem.
	\end{hint}
\end{problem}

\begin{problem}
	[\Cref{lem:vol_OK_mesh}]
	\label{prob:OK_linalg}
	Consider the composition of the embeddings $K \injto \RR^{r_1} \times \CC^{r_2} \taking\sim \RR^n$.
	Show that the image of $\OO_K \subseteq K$ has mesh equal to
	\[ \frac{1}{2^{r_2}} \sqrt{\left\lvert \Delta_K \right\rvert}. \]
	\begin{hint}
		Linear algebra.
	\end{hint}
\end{problem}

\begin{problem}
	Let $p \equiv 1 \pmod 4$ be a prime.
	Show that there are unique integers $a > b > 0$ such that $a^2+b^2=p$.
	\begin{hint}
		Factor in $\QQ(i)$.
	\end{hint}
%	\begin{sol}
%		Let's factor $(p)$ in $\QQ(i)$, which has ring of integers $\ZZ[i]$.
%		Using \Cref{thm:factor_alg}, we get $\ZZ[x] / (p,x^2+1) \cong \FF_p[x] / (x^2+1)$.
%		Since $p \equiv 1 \pmod 4$, $x^2+1 \equiv (x+t)(x-t) \pmod p$ for some $t$.
%		Thus $(p) = (p, t+i)(p, t-i)$ is the full decomposition into prime factors.
%	\end{sol}
\end{problem}


\begin{problem}
	[Korea national olympiad 2014]
	Let $p$ be an odd prime and $k$ a positive integer such that $p \mid k^2+5$.
	Prove that there exist positive integers $m$, $n$ such that $p^2 = m^2+5n^2$.
	\begin{hint}
		Factor $p$, show that the class group of $\QQ(\sqrt{-5})$ has order two.
	\end{hint}
	\begin{sol}
		Let $K = \QQ(\sqrt{-5})$. Check that $\Cl_K$ has order two using the Minkowski bound;
		moreover $\Delta_K = 20$.
		Now note that $\OO_K = \ZZ[\sqrt{-5}]$, and $x^2+5$ factors mod $p$ as $(x+k)(x-k)$;
		hence in $\OO_K$ we have $(p) = (p, \sqrt{-5}+k)(p, \sqrt{-5}-k) = \kp_1 \kp_2$, say.
		For $p > 5$ the prime $p$ does not ramify and we have $\kp_1 \neq \kp_2$, since $\Delta_K = 20$.

		Then $(p^2) = \kp_1^2 \cdot \kp_2^2$. Because the class group has order two,
		both $\kp_1^2$ and $\kp_2^2$ are principal, and because $\kp_1 \neq \kp_2$ they are distinct.
		Thus $p^2$ is a nontrivial product of two elements of $\OO_K$; from this we can extract the desired factorization.
	\end{sol}
\end{problem}
